#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdarg.h>

#include "imbus_internal.h"
#include "im_unicode.h"
#include "im_text.h"
#include "im_string.h"
#include "im_hash.h"

#define IM_STRING_MAX_CAPACITY  (IM_MAXINT32 - 8)

#define ISUPPER(c)        ((c) >= 'A' && (c) <= 'Z')
#define ISLOWER(c)        ((c) >= 'a' && (c) <= 'z')
#define ISALPHA(c)        (ISUPPER (c) || ISLOWER (c))
#define TOUPPER(c)        (ISLOWER (c) ? (c) - 'a' + 'A' : (c))
#define TOLOWER(c)        (ISUPPER (c) ? (c) - 'A' + 'a' : (c))

/************************** Declaration of internal functions ***************/
static void     __im_string_initialize  (IMPointer       string);
static void     __im_string_finalize    (IMPointer       string);
static void     __im_string_copy        (IMPointer       dest,
                                         IMConstPointer  src);
static IMBool   __im_string_serialize   (IMConstPointer  obj,
                                         IMPointer       stream);
static IMBool   __im_string_deserialize (IMPointer       obj,
                                         IMPointer       stream);
static void     __im_string_class_init  (IMPointer       klass);

static void     __im_string_ensure_size (IMString       *string,
                                         IMSize          add_size);

static IMBool   __im_string_insert_printf_internal (IMString        *string,
                                                    IMSize           pos,
                                                    const IMChar    *format,
                                                    va_list          args);

/****************** Declaration of object and class structure ************/
struct _IMString
{
    IMObject object;

    IMChar  *data;

    IMSize   length;
    IMSize   capacity;     /* IM_STRING_NPOS for static string */
};

struct _IMStringClass
{
    IMObjectClass parent_class;
};

/************************ Internal varable ************************/
static const IMObjectClass *__im_string_parent_class = 0;

/************* Implementation of internal functions ***************/
static void
__im_string_initialize (IMPointer string)
{
    ((IMString*)string)->data     = 0;
    ((IMString*)string)->length   = 0;
    ((IMString*)string)->capacity = 0;
}

static void
__im_string_finalize (IMPointer string)
{
    IMString *s = IM_STRING (string);

    _im_assert (s != 0);

    /* Free dynamic string */
    if (s->data && s->capacity != IM_STRING_NPOS)
        im_free (s->data);
}

static void
__im_string_copy (IMPointer dest, IMConstPointer src)
{
    IMString       *dp = IM_STRING (dest);
    const IMString *sp = IM_CONST_STRING (src);

    _im_assert (dp && sp);

    __im_string_finalize (dest);

    dp->data     = sp->data;
    dp->length   = sp->length;
    dp->capacity = (sp->capacity == IM_STRING_NPOS ? IM_STRING_NPOS : sp->length);

    if (sp->data && sp->capacity != IM_STRING_NPOS) {
        dp->data = im_new(IMChar, sp->length + 1);
        _im_assert (dp->data);
        memcpy (dp->data, sp->data, sp->length * sizeof (IMChar));
        dp->data [dp->length] = 0;
    }

    /* Call copy method of parent class */
    __im_string_parent_class->copy (dest, src);
}

static IMBool
__im_string_serialize (IMConstPointer obj, IMPointer stream)
{
    const IMString *str = IM_CONST_STRING (obj);
    IMStream       *sp = IM_STREAM (stream);

    _im_assert (str && sp);

    /* Call parent serialize method */
    return __im_string_parent_class->serialize (obj, stream) &&
           im_stream_put_c_string (sp, str->data, str->length);
}

static IMBool
__im_string_deserialize (IMPointer obj, IMPointer stream)
{
    IMString *str = IM_STRING (obj);
    IMStream *sp = IM_STREAM (stream);
    IMSize    len;

    _im_assert (str && sp);

    /* Call parent deserialize method */
    if (!__im_string_parent_class->deserialize (obj, stream))
        return FALSE;

    if (im_stream_get_data_type (sp) != IM_TYPE_C_STRING)
        return FALSE;

    im_string_clear (str);

    len = im_stream_get_data_size (sp);

    if (len) {
        __im_string_ensure_size (str, len);

        if (!im_stream_get_c_string (sp, str->data, len + 1))
            return FALSE;

        str->data [len] = 0;
        str->length = len;
    }

    return TRUE;
}

static void
__im_string_class_init (IMPointer klass)
{
    IMObjectClass *cp = (IMObjectClass *)klass;

    cp->copy        = __im_string_copy;
    cp->serialize   = __im_string_serialize;
    cp->deserialize = __im_string_deserialize;

    __im_string_parent_class = im_object_class_get_parent (cp);
}

static void
__im_string_ensure_size (IMString *string, IMSize add_size)
{
    _im_assert (string->length + add_size < IM_STRING_MAX_CAPACITY);

    if (string->capacity == IM_STRING_NPOS) {
        IMChar *new_data = im_new (IMChar, add_size + string->length + 1);

        _im_assert (new_data != 0);

        memcpy (new_data, string->data, string->length);

        new_data [string->length] = 0;

        string->data     = new_data;
        string->capacity = string->length + add_size;
    } else if (string->length + add_size > string->capacity) {
        IMSize     new_cap;
        IMChar *new_data;

        new_cap = string->length + add_size;

        /* The below implements an exponential growth policy */
        if (new_cap + 1 < string->capacity * 2)
            new_cap = string->capacity * 2 - 1;

        new_data = im_renew (IMChar, string->data, new_cap + 1);

        _im_assert (new_data != 0);

        string->data     = new_data;
        string->capacity = new_cap;
    }
}

/************* Implementation of public functions ***************/
void
__im_type_register_string ()
{
    static IMTypeInfo im_string_type_info = 
    {
        sizeof (IMStringClass),     /**< class_size >**/
        __im_string_class_init,     /**< class_init >**/
        0,                          /**< class_finalize >**/

        sizeof (IMString),          /**< instance_size >**/
        __im_string_initialize,     /**< instance_init >**/
        __im_string_finalize,       /**< instance_finalize >**/
    };

    __im_type_register_builtin_class (IM_TYPE_OBJECT,
                                      IM_TYPE_STRING,
                                      "String",
                                      &im_string_type_info,
                                      TRUE);
}

IMString*
im_string_new (const IMChar *cstr)
{
    IMString *s = (IMString *) im_object_new (IM_TYPE_STRING);

    _im_assert (s != 0);

    return ((cstr && *cstr) ? im_string_assign (s, cstr, (IMSize)(-1)) : s);
}

IMString*
im_string_new_length (const IMChar *cstr, IMSize length)
{
    IMString *s = (IMString *) im_object_new (IM_TYPE_STRING);

    _im_assert (s != 0);

    return ((cstr && *cstr) ? im_string_assign (s, cstr, length) : s);
}

IMString*
im_string_new_static (const IMChar *cstr)
{
    IMString *s = (IMString *) im_object_new (IM_TYPE_STRING);

    _im_assert (s != 0);

    return ((cstr && *cstr) ? im_string_assign_static (s, cstr) : s);
}

IMString*
im_string_new_reserved (IMSize capacity)
{
    IMString *s = (IMString *) im_object_new (IM_TYPE_STRING);

    _im_assert (s != 0);

    __im_string_ensure_size (s, capacity);

    return s;
}

IMString*
im_string_new_from_printf (const IMChar *format, ...)
{
    IMString *s = (IMString *) im_object_new (IM_TYPE_STRING);
    va_list ap;

    _im_assert (s != 0);

    va_start(ap, format);
    __im_string_insert_printf_internal (s, 0, format, ap);
    va_end (ap);

    return s;
}

IMString*
im_string_new_from_text_utf8 (IMConstPointer text)
{
    IMString *s;

    _im_return_val_if_fail (IM_IS_TEXT (text), 0);

    s = (IMString *) im_object_new (IM_TYPE_STRING);

    _im_assert (s != 0);

    return im_string_assign_text_utf8 (s, text);
}

void
im_string_clear (IMString *string)
{
    _im_return_if_fail (IM_IS_STRING (string));

    string->length = 0;

    if (string->capacity == IM_STRING_NPOS) {
        string->capacity = 0;
        string->data = 0;
    }
}

void
im_string_reserve (IMString *string, IMSize size)
{
    _im_return_if_fail (IM_IS_STRING (string));

    if (size > string->length)
        __im_string_ensure_size (string, size - string->length);
}

IMSize
im_string_capacity (const IMString *string)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    return string->capacity;
}

IMBool
im_string_empty (const IMString *string)
{
    _im_return_val_if_fail (IM_IS_STRING (string), TRUE);

    return string->length == 0;
}

void
im_string_resize (IMString *string, IMSize new_size, IMChar fill_ch)
{
    _im_return_if_fail (IM_IS_STRING (string));

    if (new_size < string->length) {
        /* resizing a static string. make a copy. */
        if (string->capacity == IM_STRING_NPOS) {
            IMChar *str = string->data;

            string->data = 0;
            string->length = 0;
            string->capacity = 0;

            if (new_size) {
                __im_string_ensure_size (string, new_size);
                memcpy (string->data, str, new_size);
            }
        }
        string->length = new_size;

        if (string->data)
            string->data [new_size] = 0;
    } else if (new_size > string->length) {
        __im_string_ensure_size (string, new_size - string->length);

        memset (string->data + string->length, fill_ch, new_size - string->length);

        string->length = new_size;
        string->data [new_size] = 0;
    }
}

IMSize
im_string_length (const IMString *string)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    return string->length;
}

IMUInt
im_string_hash (const IMString *string)
{
    const IMChar *cstr = im_string_c_str (string);

    return cstr ? im_str_hash (cstr) : 0;
}

const IMChar*
im_string_c_str (const IMString *string)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    /* Only for dynamic string*/
    if (string->capacity != IM_STRING_NPOS) {
        /* make sure that a valid string will always be returned. */
        if (!string->data)
            __im_string_ensure_size ((IMString *) string, 1);

        /* make sure it's 0 terminated. */
        string->data [string->length] = 0;
    }

    return string->data;
}

IMString*
im_string_assign (IMString *string, const IMChar *cstr, IMSize len)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    im_string_clear (string);

    if (cstr && *cstr && len != 0) {
        if (len == (IMSize)(-1))
            len = strlen (cstr);
        else
            len = IM_MIN (strlen (cstr), len);

        __im_string_ensure_size (string, len);

        memcpy (string->data, cstr, len);

        string->data [len] = 0;
        string->length = len;
    }

    return string;
}

IMString*
im_string_assign_static (IMString *string, const IMChar *cstr)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    __im_string_finalize (string);

    if (cstr) {
        string->data = (IMChar *) cstr;
        string->length = strlen (cstr);
        string->capacity = IM_STRING_NPOS;
    } else {
        string->data = 0;
        string->length = 0;
        string->capacity = 0;
    }

    return string;
}

IMString*
im_string_assign_text_utf8 (IMString *string, IMConstPointer text)
{
    IMSize len;

    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (IM_IS_TEXT (text), 0);

    im_string_clear (string);

    len = im_text_utf8_length (IM_CONST_TEXT (text));

    if (len) {
        __im_string_ensure_size (string, len);
        len = im_text_to_utf8_string (IM_CONST_TEXT (text), string->data, string->capacity);
        string->data [len] = 0;
        string->length = len;
    }
 
    return string;
}

IMChar
im_string_get_char (const IMString *string, IMSize idx)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (idx < string->length, 0);

    return string->data [idx];
}

void
im_string_set_char (IMString *string, IMSize idx, IMChar ch)
{
    _im_return_if_fail (IM_IS_STRING (string));
    _im_return_if_fail (idx < string->length);

    /* If the string is static, make a copy. */
    if (string->capacity == IM_STRING_NPOS)
        __im_string_ensure_size (string, 0);

    string->data [idx] = ch;
}

IMString*
im_string_get_sub_string (const IMString *string, IMSize pos, IMSize len)
{
    IMString *new_string;

    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    new_string = im_string_new (0);

    _im_assert (new_string);

    if (pos < string->length && len) {
        len = IM_MIN (len, string->length - pos);
        __im_string_ensure_size (new_string, len);
        memcpy (new_string->data, im_string_c_str (string) + pos, len);
        new_string->data [len] = 0;
        new_string->length = len;
    }

    return new_string;
}

IMString*
im_string_prepend (IMString *string, const IMString *other)
{
    return im_string_insert (string, 0, other);
}

IMString*
im_string_prepend_str (IMString *string, const IMChar *other, IMSize len)
{
    return im_string_insert_str (string, 0, other, len);
}

IMString*
im_string_prepend_char (IMString *string, IMChar ch)
{
    return im_string_insert_char (string, 0, ch);
}

IMString*
im_string_append (IMString *string, const IMString *other)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    return im_string_insert (string, string->length, other);
}

IMString*
im_string_append_str (IMString *string, const IMChar *other, IMSize len)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    return im_string_insert_str (string, string->length, other, len);
}

IMString*
im_string_append_char (IMString *string, IMChar ch)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    return im_string_insert_char (string, string->length, ch);
}

IMString*
im_string_insert (IMString *string, IMSize pos, const IMString *other)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (IM_IS_STRING (other), 0);
    _im_return_val_if_fail (pos <= string->length, 0);

    if (!other->length) return string;

    __im_string_ensure_size (string, other->length);

    if (pos < string->length)
        memmove (string->data + pos + other->length, string->data + pos, (string->length - pos) * sizeof (IMChar));

    memcpy (string->data + pos, other->data, other->length * sizeof (IMChar));

    string->length += other->length;
    string->data [string->length] = 0;

    return string;
}

IMString*
im_string_insert_str (IMString *string, IMSize pos, const IMChar *other, IMSize len)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (other || len == 0, 0);
    _im_return_val_if_fail (pos <= string->length, 0);

    if (len == 0 || !*other) return string;

    if (len == (IMSize)(-1))
        len = strlen (other);
    else
        len = IM_MIN (strlen (other), len);

    __im_string_ensure_size (string, len);

    if (pos < string->length)
        memmove (string->data + pos + len, string->data + pos, (string->length - pos) * sizeof (IMChar));

    memcpy (string->data + pos, other, len * sizeof (IMChar));

    string->length += len;
    string->data [string->length] = 0;

    return string;
}

IMString*
im_string_insert_char (IMString *string, IMSize pos, IMChar ch)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (ch != 0, 0);
    _im_return_val_if_fail (pos <= string->length, 0);

    __im_string_ensure_size (string, 1);

    if (pos < string->length)
        memmove (string->data + pos + 1, string->data + pos, (string->length - pos) * sizeof (IMChar));

    string->data [pos] = ch;
    ++ string->length;
    string->data [string->length] = 0;

    return string;
}

IMString*
im_string_erase (IMString *string, IMSize pos, IMSize len)
{
    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    if (pos >= string->length || len == 0)
        return string;

    /* If the string is static, make a copy. */
    if (string->capacity == IM_STRING_NPOS)
        __im_string_ensure_size (string, 0);

    /* erase range extents to the end of string, the
     * string will be truncated */
    if (pos + len < string->length)
        memmove (string->data + pos, string->data + pos + len, (string->length - pos - len) * sizeof (IMChar));

    string->length -= IM_MIN(len, string->length - pos);
    string->data [string->length] = 0;

    return string;
}

IMInt
im_string_compare (const IMString *string1, const IMString *string2)
{
    const IMChar *cstr1 = im_string_c_str (string1);
    const IMChar *cstr2 = im_string_c_str (string2);
    _im_assert (cstr1 && cstr2);
    return strcmp (cstr1, cstr2);
}

IMInt
im_string_n_compare (const IMString *string1, const IMString *string2, IMSize len)
{
    const IMChar *cstr1 = im_string_c_str (string1);
    const IMChar *cstr2 = im_string_c_str (string2);
    _im_assert (cstr1 && cstr2);
    return strncmp (cstr1, cstr2, len);
}

IMInt
im_string_ascii_case_compare (const IMString *string1, const IMString *string2)
{
    IMInt c1, c2;

    const IMChar *cstr1 = im_string_c_str (string1);
    const IMChar *cstr2 = im_string_c_str (string2);
    _im_assert (cstr1 && cstr2);
    while (*cstr1 && *cstr2) {
        c1 = (IMInt)(IMUChar) TOLOWER (*cstr1);
        c2 = (IMInt)(IMUChar) TOLOWER (*cstr2);
        if (c1 != c2)
            return (c1 - c2);
        cstr1++; cstr2++;
    }

    return (((IMInt)(IMUChar) *cstr1) - ((IMInt)(IMUChar) *cstr2));
}

IMInt
im_string_ascii_n_case_compare (const IMString *string1, const IMString *string2, IMSize len)
{
    IMInt c1, c2;

    const IMChar *cstr1 = im_string_c_str (string1);
    const IMChar *cstr2 = im_string_c_str (string2);
    _im_assert (cstr1 && cstr2);
    while (len && *cstr1 && *cstr2) {
        --len;
        c1 = (IMInt)(IMUChar) TOLOWER (*cstr1);
        c2 = (IMInt)(IMUChar) TOLOWER (*cstr2);
        if (c1 != c2)
            return (c1 - c2);
        cstr1++; cstr2++;
    }

    if (len)
        return (((IMInt)(IMUChar) *cstr1) - ((IMInt)(IMUChar) *cstr2));
    else
        return 0;
}

IMInt
im_string_compare_str (const IMString *string1, const IMChar *string2)
{
    const IMChar *cstr1 = im_string_c_str (string1);
    _im_assert (cstr1 && string2);
    return strcmp (cstr1, string2);
}

IMInt
im_string_n_compare_str (const IMString *string1, const IMChar *string2, IMSize len)
{
    const IMChar *cstr1 = im_string_c_str (string1);
    _im_assert (cstr1 && string2);
    return strncmp (cstr1, string2, len);
}

IMInt
im_string_ascii_case_compare_str (const IMString *string1, const IMChar *string2)
{
    IMInt c1, c2;
    const IMChar *cstr1 = im_string_c_str (string1);
    _im_assert (cstr1 && string2);
    while (*cstr1 && *string2) {
        c1 = (IMInt)(IMUChar) TOLOWER (*cstr1);
        c2 = (IMInt)(IMUChar) TOLOWER (*string2);
        if (c1 != c2)
            return (c1 - c2);
        cstr1++; string2++;
    }

    return (((IMInt)(IMUChar) *cstr1) - ((IMInt)(IMUChar) *string2));
}

IMInt
im_string_ascii_n_case_compare_str (const IMString *string1, const IMChar *string2, IMSize len)
{
    IMInt c1, c2;
    const IMChar *cstr1 = im_string_c_str (string1);
    _im_assert (cstr1 && string2);
    while (len && *cstr1 && *string2) {
        --len;
        c1 = (IMInt)(IMUChar) TOLOWER (*cstr1);
        c2 = (IMInt)(IMUChar) TOLOWER (*string2);
        if (c1 != c2)
            return (c1 - c2);
        cstr1++; string2++;
    }

    if (len)
        return (((IMInt)(IMUChar) *cstr1) - ((IMInt)(IMUChar) *string2));
    else
        return 0;
}

static IMBool
__im_string_insert_printf_internal (IMString *string, IMSize pos, const IMChar *format, va_list args)
{
    IMInt n, size = 100;
    IMChar *p, *np;

    /* Guess we need no more than 100 bytes. */
    p = im_malloc (size);

    _im_assert (p != 0);

    while (p) {
        /* Try to print in the allocated space. */
        n = vsnprintf (p, size, format, args);

        /* If that worked, return the string. */
        if (n > -1 && n < size)
            break;

        /* Else try again with more space. */
        if (n > -1)    /* glibc 2.1 */
            size = n+1; /* precisely what is needed */
        else           /* glibc 2.0 */
            size *= 2;  /* twice the old size */

        np = im_realloc (p, size);

        _im_assert (np != 0);

        if (!np) im_free (p);

        p = np;
    }

    if (p) {
        im_string_insert_str (string, pos, p, n);
        im_free (p);
        return TRUE;
    } else {
        _im_assert_not_reached ("vsnprintf shouldn't fail. It maybe out of memory or you have a bogus vsnprintf.");
    }

    return FALSE;
}

IMString*
im_string_prepend_printf (IMString *string, const IMChar *format, ...)
{
    IMBool res;
    va_list ap;

    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    va_start(ap, format);
    res = __im_string_insert_printf_internal (string, 0, format, ap);
    va_end (ap);

    return res ? string : 0;
}

IMString*
im_string_append_printf (IMString *string, const IMChar *format, ...)
{
    IMBool res;
    va_list ap;

    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    va_start(ap, format);
    res = __im_string_insert_printf_internal (string, string->length, format, ap);
    va_end (ap);

    return res ? string : 0;
}

IMString*
im_string_insert_printf (IMString *string, IMSize pos, const IMChar *format, ...)
{
    IMBool res;
    va_list ap;

    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (pos <= string->length, 0);

    va_start(ap, format);
    res = __im_string_insert_printf_internal (string, pos, format, ap);
    va_end (ap);

    return res ? string : 0;
}

IMString*
im_string_printf (IMString *string, const IMChar *format, ...)
{
    IMBool res;
    va_list ap;

    _im_return_val_if_fail (IM_IS_STRING (string), 0);

    im_string_clear (string);

    va_start(ap, format);
    res = __im_string_insert_printf_internal (string, 0, format, ap);
    va_end (ap);

    return res ? string : 0;
}

IMSize
im_string_find (const IMString *string, const IMString *other, IMSize pos)
{
    const IMChar *p;
    const IMChar *end;
    IMSize i;

    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);
    _im_return_val_if_fail (IM_IS_STRING (other), IM_STRING_NPOS);

    if (pos >= string->length)
        return IM_STRING_NPOS;

    if (other->length == 0)
        return pos;

    if (other->length > string->length - pos)
        return IM_STRING_NPOS;

    p = string->data + pos;
    end = string->data + string->length - other->length;

    while (*p && p <= end) {
        for (i = 0; i < other->length; ++i)
            if (p[i] != other->data[i])
                goto next;
 
        return p - string->data;

        next:
        ++p;
    }
 
    return IM_STRING_NPOS;
}

IMSize
im_string_find_str (const IMString *string, const IMChar *other, IMSize pos, IMSize len)
{
    const IMChar *p;
    const IMChar *end;
    IMSize i;

    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);

    if (pos >= string->length)
        return IM_STRING_NPOS;

    if (!other || !*other || !len)
        return pos;

    if (len == (IMSize)(-1))
        len = strlen (other);
    else
        len = IM_MIN (strlen (other), len);

    if (len > string->length - pos)
        return IM_STRING_NPOS;

    p = string->data + pos;
    end = string->data + string->length - len;

    while (*p && p <= end) {
        for (i = 0; i < len; ++i)
            if (p[i] != other[i])
                goto next;
 
        return p - string->data;

        next:
        ++p;
    }
 
    return IM_STRING_NPOS;
}

IMSize
im_string_find_char (const IMString *string, IMChar ch, IMSize pos)
{
    const IMChar *p;
    const IMChar *end;

    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);

    if (pos >= string->length)
        return IM_STRING_NPOS;

    p = string->data + pos;
    end = string->data + string->length - 1;

    for (; *p && p <= end; ++p)
        if (*p == ch)
            return p - string->data;
 
    return IM_STRING_NPOS;
}

IMSize
im_string_rfind (const IMString *string, const IMString *other, IMSize pos)
{
    const IMChar *p;
    IMSize i;

    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);
    _im_return_val_if_fail (IM_IS_STRING (other), IM_STRING_NPOS);

    if (string->length < other->length)
        return IM_STRING_NPOS;

    if (other->length == 0)
        return 0;

    if (pos == IM_STRING_NPOS || pos + other->length > string->length)
        pos = string->length - other->length;

    p = string->data + pos;

    while (p >= string->data) {
        for (i = 0; i < other->length; ++i)
            if (p[i] != other->data[i])
                goto next;
 
        return p - string->data;

        next:
        --p;
    }
 
    return IM_STRING_NPOS;
}
IMSize
im_string_rfind_str (const IMString *string, const IMChar *other, IMSize pos, IMSize len)
{
    const IMChar *p;
    IMSize i;

    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);
    _im_return_val_if_fail (IM_IS_STRING (other), IM_STRING_NPOS);

    if (len == IM_STRING_NPOS)
        len = strlen (other);
    else
        len = IM_MIN (strlen (other), len);

    if (string->length < len)
        return IM_STRING_NPOS;

    if (len == 0)
        return 0;

    if (pos == IM_STRING_NPOS || pos + len > string->length)
        pos = string->length - len;

    p = string->data + pos;

    while (p >= string->data) {
        for (i = 0; i < len; ++i)
            if (p[i] != other[i])
                goto next;
 
        return p - string->data;

        next:
        --p;
    }
 
    return IM_STRING_NPOS;
}
IMSize
im_string_rfind_char (const IMString *string, IMChar ch, IMSize pos)
{
    const IMChar *p;

    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);

    p = string->data + IM_MIN(string->length - 1, pos);

    for (;p >= string->data; --p)
        if (*p == ch)
            return p - string->data;
 
    return IM_STRING_NPOS;
}
IMSize
im_string_find_first_of (const IMString *string, const IMString *other, IMSize pos)
{
    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);
    _im_return_val_if_fail (IM_IS_STRING (other), IM_STRING_NPOS);

    if (string->length == 0 || other->length == 0)
        return IM_STRING_NPOS;

    for (; pos < string->length; ++pos)
        if (memchr (other->data, string->data[pos], other->length))
            return pos;

    return IM_STRING_NPOS;
}
IMSize
im_string_find_first_of_str (const IMString *string, const IMChar *other, IMSize pos, IMSize len)
{
    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);
    _im_return_val_if_fail (other != 0, IM_STRING_NPOS);

    if (len == IM_STRING_NPOS)
        len = strlen (other);
    else
        len = IM_MIN (strlen (other), len);

    if (string->length == 0 || len == 0)
        return IM_STRING_NPOS;

    for (; pos < string->length; ++pos)
        if (memchr (other, string->data[pos], len))
            return pos;

    return IM_STRING_NPOS;
}
IMSize
im_string_find_last_of (const IMString *string, const IMString *other, IMSize pos)
{
    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);
    _im_return_val_if_fail (IM_IS_STRING (other), IM_STRING_NPOS);

    if (string->length == 0 || other->length == 0)
        return IM_STRING_NPOS;

    for (pos = IM_MIN (string->length - 1, pos); pos >= 0; --pos)
        if (memchr (other->data, string->data[pos], other->length))
            return pos;

    return IM_STRING_NPOS;
}
IMSize
im_string_find_last_of_str (const IMString *string, const IMChar *other, IMSize pos, IMSize len)
{
    _im_return_val_if_fail (IM_IS_STRING (string), IM_STRING_NPOS);
    _im_return_val_if_fail (other != 0, IM_STRING_NPOS);

    if (len == IM_STRING_NPOS)
        len = strlen (other);
    else
        len = IM_MIN (strlen (other), len);

    if (string->length == 0 || len == 0)
        return IM_STRING_NPOS;

    for (pos = IM_MIN (string->length - 1, pos); pos >= 0; --pos)
        if (memchr (other, string->data[pos], len))
            return pos;

    return IM_STRING_NPOS;
}
void
im_string_ascii_tolower (IMString *string)
{
    im_string_ascii_tolower_range (string, 0, IM_STRING_NPOS);
}
void
im_string_ascii_toupper (IMString *string)
{
    im_string_ascii_toupper_range (string, 0, IM_STRING_NPOS);
}
void
im_string_ascii_tolower_range (IMString *string, IMSize pos, IMSize len)
{
    IMSize i;

    _im_return_if_fail (IM_IS_STRING (string));

    /* If the string is static, make a copy. */
    if (string->capacity == IM_STRING_NPOS)
        __im_string_ensure_size (string, 0);

    for (i = pos; (i - pos) < len && i < string->length; ++i)
        string->data[i] = TOLOWER (string->data[i]);
}
void
im_string_ascii_toupper_range (IMString *string, IMSize pos, IMSize len)
{
    IMSize i;

    _im_return_if_fail (IM_IS_STRING (string));

    /* If the string is static, make a copy. */
    if (string->capacity == IM_STRING_NPOS)
        __im_string_ensure_size (string, 0);

    for (i = pos; (i - pos) < len && i < string->length; ++i)
        string->data[i] = TOUPPER (string->data[i]);
}

void
im_string_trim_blanks (IMString *string)
{
    IMSize start;
    IMSize end;
    IMSize len;
    IMChar c;
    _im_return_if_fail (IM_IS_STRING (string));
    /* Copy it first if it's a static string */
    if (string->capacity == IM_STRING_NPOS)
        __im_string_ensure_size (string, 0);
    for (start = 0; start < string->length; ++start) {
        c = string->data[start];
        if (c != ' ' && c != '\t' && c != '\v' && c != '\n')
            break;
    }
    for (end = string->length; end > 0; --end) {
        c = string->data[end - 1];
        if (c != ' ' && c != '\t' && c != '\v' && c != '\n')
            break;
    }
    len = end - start;
    if (len) {
      memmove(string->data, string->data + start, len);
      string->data[len] = 0;
      string->length = len;
    } else {
      im_string_clear(string);
    }
}

IMObjectArray*
im_string_split (const IMString *string, const IMChar *delim_chars)
{
    IMObjectArray *array;
    IMString *sub;
    IMSize start = 0;
    IMSize end = 0;
    IMSize i;
    IMSize delim_len;
    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (delim_chars && *delim_chars, 0);
    array = im_object_array_new();
    _im_assert(array);
    delim_len = strlen(delim_chars);
    for (end = 0; end < string->length; ++end) {
        if (memchr (delim_chars, string->data[end], delim_len)) {
            sub = im_string_get_sub_string (string, start, end - start);
            _im_assert(sub);
            im_object_array_append (array, sub);
            start = end + 1;
        }
    }
    if (start < end) {
        sub = im_string_get_sub_string (string, start, end - start);
        _im_assert(sub);
        im_object_array_append (array, sub);
    }
    return array;
}

IMString*
im_string_get_left_portion (const IMString *string, const IMChar *delim_chars)
{
    IMString *result;
    IMSize pos;
    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (delim_chars && *delim_chars, 0);
    pos = im_string_find_first_of_str (string, delim_chars, 0, -1);
    result = im_string_get_sub_string (string, 0, pos);
    _im_assert(result);
    im_string_trim_blanks (result);
    return result;
}

IMString*
im_string_get_right_portion (const IMString *string, const IMChar *delim_chars)
{
    IMString *result;
    IMSize pos;
    _im_return_val_if_fail (IM_IS_STRING (string), 0);
    _im_return_val_if_fail (delim_chars && *delim_chars, 0);
    pos = im_string_find_first_of_str (string, delim_chars, 0, -1);
    if (pos != IM_STRING_NPOS)
        result = im_string_get_sub_string (string, pos+1, IM_STRING_NPOS);
    else
        result = im_string_new (0);
    _im_assert(result);
    im_string_trim_blanks (result);
    return result;
}


/*
vi:ts=4:nowrap:ai:expandtab
*/
